import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-05-10
 * Time: 17:37
 */

class Solution2 {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        char tmp =0;
        for(int i =0;i<s.length();++i){
            char c1 = chars[i];
            if(c1=='['||c1=='('||c1=='{'){
                stack.push(c1);
                tmp = c1;
            }else {
                char c2 = chars[i];
                if(tmp=='[' && c2==']'||tmp=='{' && c2=='}' ||
                        tmp=='(' && c2==')'){
                    //如果发现匹配就弹栈
                    stack.pop();
                }
            }
        }
        if(stack.empty()){
            return true;
        }else{
            return false;
        }
    }
}


class Solution1 {
    public boolean isValid(String s) {
        if((s.length()%2)!=0) {
            return false;
        }
        Stack<Character> stack = new Stack<Character>();
        char charArray[] = s.toCharArray();
        for(int i=0;i< charArray.length;++i) {
            if(charArray[i]=='(') {
                stack.push('(');
            } else if(charArray[i]=='[') {
                stack.push('[');
            } else if(charArray[i]=='{') {
                stack.push('{');
            } else {
                if(stack.isEmpty()) {
                    return false;
                }
                char top =stack.peek();
                if(top=='('&&charArray[i]==')'||top=='['&&charArray[i]==']'||
                        top=='{'&&charArray[i]=='}'){
                    stack.pop();
                }else {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}


class Solution4 {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int j =0;
        for(int i =0;i<pushed.length;++i){
            stack.push(pushed[i]);
            while(!stack.empty()&&j<popped.length&&stack.peek()==popped[j]){
                stack.pop();
                ++j;
            }
        }
        return stack.empty();
    }
}

class Solution8{
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(int i =0;i<tokens.length;++i){
            if(!isOperation(tokens[i])){
                int x = Integer.parseInt(tokens[i]);
                stack.push(x);//如果是整数就入栈
            }else {
                //是+-*/
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch((tokens[i])){
                    case "+":
                        stack.push(num1+num2);
                        break;
                    case "-":
                        stack.push(num1-num2);
                        break;
                    case "*":
                        stack.push(num1*num2);
                        break;
                    case "/":
                        stack.push(num1/num2);
                        break;
                }
            }
        }
        return stack.pop();
    }
    private Boolean isOperation(String s){
        char[] chars = s.toCharArray();
        if(chars[0]=='+'||chars[0]=='-'||chars[0]=='*'||chars[0]=='/'){
            return true;
        }
        return false;
    }
}
//class Solution5 {
//    static class ListNode{
//        private ListNode next;
//        private int val;
//        public ListNode(int val){
//            this.val = val;
//        }
//    }
//    public ListNode reverseKGroup(ListNode head, int k) {
//        ListNode dummyHead = new ListNode(-1);
//        dummyHead.next = head;
//        ListNode prev = dummyHead;
//        ListNode end = dummyHead;
//        while(end.next!=null){
//            //先让end走k步,使得end走到要反转链表的最后一个节点
//            for(int i =0;end!=null&&i<k;++i){
//                end = end.next;
//            }
//            //这时要判断一下end有可能走到null，也就是反转的链表的节点小于k
//            if(end==null){
//                break;
//            }
//            //定义start是反转链表的头结点
//            ListNode start = prev.next;
//            //反转链表的时候要将prev与start后面断开等反转之后在连接
//            prev.next =null;
//            //在将end与后面节点断开时要保存end节点的下一个等反转之后在连接
//            ListNode next = end.next;
//            end.next = null;//与end后面节点进行断开
//            prev.next = reverseList(start);//反转之后的链表与start连接
//            start.next = next;//此时start位于end之前的位置，这时要将start与后面的节点连接
//            //迭代循环重复此步骤一直到end.next为空
//            prev = start;
//            end = start;
//        }
//        return dummyHead.next;
//
//    }
//    //反转链表
//    public ListNode reverseList(ListNode head){
//        if(head==null) return null;
//        ListNode cur = head;
//        ListNode prev = null;
//        while(cur!=null){
//            ListNode curNext = cur.next;
//            cur.next= prev;
//            prev = cur;
//            cur =curNext;
//        }
//        return prev;
//    }
//}
class Solution {
    public int singleNumber(int[] nums) {
        int[] cnt = new int[32];
        //这就代表将数组中每一个元素的二进制1的个数存放到cnt数组里面
        for (int i = 0 ; i < nums.length ; i++ ) {
            int num = nums[i];
            for (int j = 0; j < 32; j++) {
                int temp = num >> j;//拿到二进制的每一位
                int x = temp & 1;//看一看每一位是1还是0
                if (x == 1) {
                    cnt[j]++;//如果是1就利用哈希表奇数,累加1的个数
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int temp = cnt[i] % 3;
            if (temp == 1) {
                int num = 1 << i;
                ans += num;
            }
        }
        return ans;
    }
}


public class LeetCode {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2,2,3,2};
        solution.singleNumber(nums);
    }

//    public static void main(String[] args) {
//        Solution solution = new Solution();
//        String[] strings = {"2","1","+","3","*"};
//        solution.evalRPN(strings);
//    }


//    public static void main1(String[] args) {
//        Solution solution = new Solution();
//        int[] pushed={1,2,3,4,5};
//        int[] popped={4,5,3,2,1};
//        solution.validateStackSequences(pushed,popped);
//        String s ="hjk";
//    }
}
